package com.markus.code.二叉树.leetcode;

import java.util.HashMap;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/12 23:22
 * todo: 根据前序和中序遍历重新构建二叉树
 */
public class LeetCode_105 {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    private HashMap<Integer,Integer> indexMap;
    private int []preorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length == 0 || preorder.length != inorder.length){
            return null;
        }
        this.preorder = preorder;
        indexMap = new HashMap<>();
        for (int i = 0 ; i < inorder.length ; i++){
            indexMap.put(inorder[i],i);
        }
        return  buildCore(0,preorder.length-1,0,inorder.length-1);
    }
    private TreeNode buildCore(int preL,int preR,int inL,int inR){
        if (preL > preR){
            return null;
        }
        int rootValue = preorder[preL];
        TreeNode root = new TreeNode(rootValue);
        int inorderIndex = indexMap.get(rootValue);
        root.left = buildCore(preL+1,preL+inorderIndex-inL,inL,inorderIndex-1);
        root.right = buildCore(preL+inorderIndex-inL+1,preR,inorderIndex+1,inR);
        return root;
    }

    private void printTreePreOrder(TreeNode root){
        if (root != null){
            System.out.print(root.val + " ");
            printTreePreOrder(root.left);
            printTreePreOrder(root.right);
        }
    }

    public static void main(String[] args) {
        int []preorder = {3,9,20,15,7};
        int []inorder = {9,3,15,20,7};
        LeetCode_105 demo = new LeetCode_105();
        TreeNode root = demo.buildTree(preorder, inorder);
         demo.printTreePreOrder(root);
    }
}
